//大西洋太平洋水流问题
class Solution {
public:
    //给一个表格 数字高的可以走到数字低的地方
    //问哪几个坐标 可以同时流入左或上区域和右或下区域
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    int m;
    int n;
    vector<vector<bool>>gotoPac;
    vector<vector<bool>>gotoAtl;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
    {
        //思路是用两个bool数组 反应某一坐标能否流入两个区域
        //从海边开始dfs看看可以从那里过来 把他置为false

        m=heights.size();
        n=heights[0].size();
        gotoAtl.resize(m,vector<bool>(n,false));
        gotoPac.resize(m,vector<bool>(n,false));
        for(int i=0;i<m;i++)
        {
            dfs(heights,gotoPac,i,0);
            dfs(heights,gotoAtl,i,n-1);
        }
        for(int j=0;j<n;j++)
        {
            dfs(heights,gotoPac,0,j);
            dfs(heights,gotoAtl,m-1,j);
        }
        vector<vector<int>>res;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(gotoAtl[i][j] && gotoPac[i][j])
                res.push_back({i,j});
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& used,int x,int y)
    {
        used[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int nx=x+arr[i][0];
            int ny=y+arr[i][1];
            if(nx>=0 && nx<m && ny>=0 &&ny<n && !used[nx][ny] && heights[nx][ny]>=heights[x][y])
            {
                dfs(heights,used,nx,ny);
            }
        }
    }
};